package util;
import java.util.*;

import org.junit.Test;

public class TreeUtils {

    public static TreeNode createTree(Integer[] arr) {
        // 使用队列来存储每一层的非空节点，下一层的数目要比上一层高
        ArrayDeque<TreeNode> pre = new ArrayDeque<>();
        TreeNode root = new TreeNode(arr[0]);
        pre.addLast(root);
        // 表示要遍历的下一个节点
        int index = 0;
        while (!pre.isEmpty()) {

            ArrayDeque<TreeNode> cur = new ArrayDeque<>();
            while (!pre.isEmpty()) {
                TreeNode node = pre.removeFirst();
                TreeNode left=null;
                TreeNode right=null;
                // 如果对应索引上的数组不为空的话就创建一个节点,进行判断的时候，
                // 要先索引看是否已经超过数组的长度，如果索引已经超过了数组的长度，那么剩下节点的左右子节点就都是空了
                // 这里index每次都会增加，实际上是不必要的，但是这样写比较简单
                if (++index<arr.length&&arr[index]!=null){
                    left=new TreeNode(arr[index]);
                    cur.addLast(left);
                }
                if (++index<arr.length&&arr[index]!=null){
                    right=new TreeNode(arr[index]);
                    cur.addLast(right);
                }
                node.left=left;
                node.right=right;
            }
            pre=cur;
        }


        return root;
    }

    /* 
        对牛客网的二叉树进行反序列化，输入格梩为：
        {1,2,3,4,#,6,7}
        这是一个层序输入的二叉树
    */
    public static TreeNode deserialization(String s) {
        if (s.startsWith("{") && s.endsWith("}"))
            s = s.substring(1, s.length() - 1);
        String[] ss = s.split(",");
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode root = new TreeNode(Integer.parseInt(ss[0]));
        queue.offer(root);
        int idx = 1;
        TreeNode left, right, cur;
        while (!queue.isEmpty() && idx < ss.length) {
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                cur = queue.poll();
                if (idx == ss.length) break;
                if (!ss[idx].equals("#")) {
                    left = new TreeNode(Integer.parseInt(ss[idx]));
                    cur.left = left;
                    queue.offer(left);
                }
                idx++;
                if (idx == ss.length) break;
                if (!ss[idx].equals("#")) {
                    right = new TreeNode(Integer.parseInt(ss[idx]));
                    cur.right = right;
                    queue.offer(right);
                }
                idx++;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        Integer[] arr = {5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1};
        // Integer[] arr={5,4};
        TreeNode tree = createTree(arr);
        prePrinTree(tree);

        TreeNode root = deserialization("{1,2,3,4,5,#,#,#,#,6}");
        printBinaryTreeVisualization(root);
    }

    private static void prePrinTree(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        prePrinTree(node.left);
        prePrinTree(node.right);
    }

    /**
                                                                        v1v         
                                                   v4v         
                                                                        ^5^         
                              v8v         
                                                  ^13^         
         H5H         
                              ^4^         
                                                                        v2v         
                                                  ^11^         
                                                                        ^7^   
                                                                        
        在可视化中，“v”“^”指向离当前节点最接近、@link[靠左]的地父节点

     */
    public static void printBinaryTreeVisualization(TreeNode root) {
        visualPrint(root, "H", 0, 21); //多了这一个调用有两个目的：1.保证根节点前后缀的特殊性，2.保证能够方便修改最大长度
    }

    /**
     * 根据所给的根节点，以横向从左往右打印二叉树【实质是一个 右 中 左 的遍历】
     * @param root
     * @param fix 描述当前子树的前后缀【根，H; other:[left:^, right：v]】 指向其中间父节点
     * @param height 当前打印串所在的打印字符串的第几行【最右节点为第一行】
     * @param len 每个节点所占的字符大小【不论何时，节点只会占据这么大】[注：long类型最大为19个数字，加上前后缀为21个]
     */
    private static void visualPrint(TreeNode root, String fix, int height, int len)  {
        if (root == null) return;
        visualPrint(root.right, "v", height + 1, len); //因为是横着看的，因此最上一个应该是右子树

        //打印一个节点的逻辑
        String mid = fix + root.val + fix;
        int lenMid;
        int lenLeft = (len - (lenMid = mid.length())) >>> 1; //左边空格数
        int lenRight = len - lenLeft - lenMid; //右边空格数
        String res = getFullString(lenLeft + height * len, lenRight, mid); //lenLeft需要加上当前层数前的空格，保证每层层次分明
        System.out.println(res);

        visualPrint(root.left, "^", height + 1, len);
    }

    public static String getFullString(int leftLen, int rightLen, String org) {
        StringBuilder sb = new StringBuilder(org);
        for (int i = 0; i < leftLen; i++) {
            sb.insert(0, " ");
        }
        for (int i = 0; i < rightLen; i++) {
            sb.append(" ");
        }
        return sb.toString();
    }

   

    @Test
    public void test() {
        Integer[] arr = {5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1};
        TreeNode root = createTree(arr);
        printBinaryTreeVisualization(root);
    }
}

